package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-24 10:18
 **/
public class LeetCode4 {

    /**
     * 使用了归并排序的合并的代码将两个升序数组合并成一个升序数组
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        //数组nums1的长度
        int size1 = nums1.length;
        //数组nums2的长度
        int size2 = nums2.length;
        //合并数组的长度
        int size = size1 + size2;
        //合并两个数组
        int[] nums = new int[size];
        //指向nums1数组当前下标
        int i = 0;
        //指向nums2数组当前下标
        int j = 0;
        //指向合并后的数组当前下标
        int index = 0;
        //由于是两个升序的数组，这边使用了归并排序合并的代码
        while (i < size1 && j < size2) {
            if (nums1[i] <= nums2[j]) {
                nums[index++] = nums1[i++];
            } else {
                nums[index++] = nums2[j++];
            }
        }
        while (i < size1) {
            nums[index++] = nums1[i++];
        }
        while (j < size2) {
            nums[index++] = nums2[j++];
        }
        if (size % 2 == 0) {
            return (double) (nums[(size - 1) / 2] + nums[(size + 1) / 2]) / 2;
        } else {
            return nums[(size - 1) / 2];
        }
    }


    /**
     * 使用了划分数组的解法，时间复杂度O(log(min(m,n)))
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //让nums1数组始终指向元素较少的那个数组,使得后一个数组的分割线两边都有元素
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        //存储数组nums1的长度
        int m = nums1.length;
        //存储数组nums2的长度
        int n = nums2.length;
        //指向数组一的左边界
        int left = 0;
        //指向数组一的右边界
        int right = m;
        //分割线左边元素的个数
        int totalLeft = (m + n + 1) / 2;
        //找到正确的分割线。
        while (left < right) {
            //当前的nums1分割线的位置
            int i = (left + right + 1) / 2;
            //当前的nums2分隔线的位置，i + j = totalLeft
            int j = totalLeft - i;
            //正确的分隔线需要满足条件nums[i - 1] < nums[j] && nums[j - 1] < nums[i]
            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                left = i;
            }
        }
        //数组1的分割线
        int split1 = left;
        //数组2的分割线
        int split2 = totalLeft - left;
        //数组1左边最大值
        int nums1LeftMax = split1 == 0 ? Integer.MIN_VALUE : nums1[split1 - 1];
        //数组1右边最小值
        int nums1RightMin = split1 == m ? Integer.MAX_VALUE : nums1[split1];
        //数组2左边最大值
        int nums2LeftMax = split2 == 0 ? Integer.MIN_VALUE : nums2[split2 - 1];
        //数组2右边最小值
        int nums2RightMin = split2 == n ? Integer.MAX_VALUE : nums2[split2];

        //如果两个数组长度之和为偶数，则其中位数为左边最大值+右边最小值 除2
        if ((m + n) % 2 == 0)  {
            return ((double) (Math.max(nums1LeftMax, nums2LeftMax)) + (Math.min(nums1RightMin, nums2RightMin))) / 2;
        } else {
            return Math.max(nums1LeftMax, nums2LeftMax);
        }

    }

    public static void main(String[] args) {
        LeetCode4 code = new LeetCode4();
        //double medianSortedArrays = code.findMedianSortedArrays(new int[]{1, 3}, new int[]{2});
        double medianSortedArrays = code.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4});
        System.out.println("medianSortedArrays = " + medianSortedArrays);
    }
}
